package com.xjj.tree;

import com.xjj.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class M0105ConstructBinaryTreeFromPreorderAndInorderTraversal {

    private Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 前序遍历,遍历树的第一个为root,后面为左右
        // 中序遍历,先左子全遍历,再右子全遍历,中间会有个root
        // 因此从前序遍历得到root,再从中序划分左右即可 分治

        // 存位置信息,避免后面循环去找
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight,
                           int[] inorder, int inLeft, int inRight) {
        // System.out.println(preLeft);
        // System.out.println(preRight);

        // 两个范围的差值是相等的,用哪个都一样
        if (preLeft > preRight) {
            // 叶子节点
            return null;
        }
        int val = preorder[preLeft];
        TreeNode root = new TreeNode(val);
        int index = map.get(val);
        // System.out.println(index);

        // 0 1 2
        // 1 0 2
        root.left = build(preorder, preLeft + 1, preLeft + (index - inLeft),
                inorder, inLeft, index - 1);
        root.right = build(preorder, preLeft + (index - inLeft) + 1, preRight,
                inorder, index + 1, inRight);
        return root;
    }
}
